package 剑指offer_day02;

import publicClass.ListNode;

/**
 * 剑指 Offer 24. 反转链表
 * 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
 *
 * 示例:
 *
 * 输入: 1->2->3->4->5->NULL
 * 输出: 5->4->3->2->1->NULL
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Offer24 {


    public ListNode reverseList(ListNode head) {

        //使用 栈 解决
        // 一种 使用快慢指针 将后面节点的指向反转


        ListNode pre = new ListNode();

        ListNode suf = new ListNode();

        if (head == null || head.next == null) { //链表为空 或者链表只有一个节点的情况
            return head;
        }


        //开始反转链表
        pre.next = head.next;
        suf.next = head;
        head.next = null; //变成尾部节点

        ListNode temp = new ListNode(); //用来保存 pre的下一个节点
        while (pre.next.next != null) { //说明还有下一个

            temp.next = pre.next.next;
            //1  后节点 指向前节点
            pre.next.next = suf.next;

            //2 向后移一位
            suf.next = pre.next;

            pre.next = temp.next;


        }

        pre.next.next = suf.next;

        return pre.next;

    }

}
